#include "basic/hs.h"

#include <cstdint>
#include <vector>
#include "basic/types.h"

namespace basic {

#define FOREST_DEPTH_SOIL -255
#define FOREST_DEPTH_NOT_EXIST -1
#define FOREST_DEPTH_ROOT 0

HSForest::HSForest() {
}

HSForest::~HSForest() {
  m_ref_pNode = nullptr;
  m_soil.m_ref_pNodeFirstChild = nullptr;
}

bool HSForest::IsRootNode(const HSNode* node) const {
  if (!node)
    return false;
  HSNode* nd = node->m_ref_pNodeParent;
  return nd ? nd == &m_soil : true;
}

bool HSForest::IsLeafNode(const HSNode* node) const {
  if (!node)
    return false;
  return node->m_ref_pNodeFirstChild == nullptr;
}

HSNode* HSForest::GetFirstChild(HSNode* node) {
  if (!node)
    node = &m_soil;
  return node->m_ref_pNodeFirstChild;
}

HSNode* HSForest::GetLastChild(HSNode* node) {
  if (!node)
    node = &m_soil;
  HSNode* _n{node->m_ref_pNodeFirstChild};
  HSNode* _nPre{nullptr};
  while (_n) {
    _nPre = _n;
    _n = _n->m_ref_pNodeNextSibling;
  }
  return _nPre;
}

HSNode* HSForest::GetSibling(HSNode* node, int offset, bool notNull) {
  if (offset == 0)
    return node;
  while (node) {
    if (offset > 0) {
      if (node->m_ref_pNodeNextSibling) {
        node = node->m_ref_pNodeNextSibling;
        --offset;
      } else {
        return notNull ? node : nullptr;
      }
    } else if (offset < 0) {
      if (node->m_ref_pNodePreSibling) {
        node = node->m_ref_pNodePreSibling;
        ++offset;
      } else
        return notNull ? node : nullptr;
    } else
      return node;
  }
  return nullptr;
}
HSNode* HSForest::GetNextSibling(HSNode* node) {
  if (!node)
    return nullptr;
  return node->m_ref_pNodeNextSibling;
}

HSNode* HSForest::GetPreSibling(HSNode* node) {
  if (!node)
    return nullptr;
  return node->m_ref_pNodePreSibling;
}

HSNode* HSForest::GetParent(HSNode* node) {
  if (!node)
    return nullptr;
  HSNode* nd = node->m_ref_pNodeParent;
  return nd == &m_soil ? nullptr : nd;
}

HSNode* HSForest::GetRoot(HSNode* node) {
  if (!node)
    return nullptr;
  while (node->m_ref_pNodeParent) {
    if (node->m_ref_pNodeParent == &m_soil)
      return node;
    node = node->m_ref_pNodeParent;
  }
  return node;
}

int HSForest::GetOffset(const HSNode* node) const {
  if (!node)
    return M_INVALID_OFFSET;
  if (!node->m_ref_pNodeParent)
    return M_INVALID_OFFSET;
  if (node->m_ref_pNodeParent == &m_soil)
    return M_INVALID_OFFSET;
  int r = 0u;
  while (node->m_ref_pNodePreSibling) {
    ++r;
    node = node->m_ref_pNodePreSibling;
  }
  return r;
}

HSNodeResult HSForest::Remove(HSNode* node) {
  if (!node)
    return HSNodeResult::RESULT_INVALID_VALUE;
  HSNode* pNode = node->m_ref_pNodeParent;
  HSNode* preNode = node->m_ref_pNodePreSibling;
  HSNode* nextNode = node->m_ref_pNodeNextSibling;

  /// rebuild sibling relation;
  if (preNode)
    preNode->m_ref_pNodeNextSibling = nextNode;
  if (nextNode)
    nextNode->m_ref_pNodePreSibling = preNode;

  /// rebuild parent relation;
  if (pNode && pNode->m_ref_pNodeFirstChild == node) {
    pNode->m_ref_pNodeFirstChild = nextNode;
  }

  node->m_ref_pNodeParent = nullptr;
  node->m_ref_pNodePreSibling = nullptr;
  node->m_ref_pNodeNextSibling = nullptr;
  return HSNodeResult::RESULT_SUCCESS;
}

HSNodeResult HSForest::Insert(HSNode* node, HSNode* desNode, HSNodeRelation relation) {
  if (!node)
    return HSNodeResult::RESULT_INVALID_VALUE;
  if (desNode == node)
    return HSNodeResult::RESULT_SAME_NODE;

  Remove(node);
  if (!desNode)
    desNode = &m_soil;

  switch (relation) {
  case HSNodeRelation::RELATION_NEXT_SIBLING: {
    HSNode* nextNode = desNode->m_ref_pNodeNextSibling;
    node->m_ref_pNodeNextSibling = nextNode;
    if (nextNode)
      nextNode->m_ref_pNodePreSibling = node;
    desNode->m_ref_pNodeNextSibling = node;
    node->m_ref_pNodePreSibling = desNode;
    node->m_ref_pNodeParent = desNode->m_ref_pNodeParent;
  } break;
  case HSNodeRelation::RELATION_PRE_SIBLING: {
    HSNode* preNode = desNode->m_ref_pNodePreSibling;
    node->m_ref_pNodePreSibling = preNode;
    if (preNode)
      preNode->m_ref_pNodeNextSibling = node;
    else
      desNode->m_ref_pNodeParent->m_ref_pNodeFirstChild = node;
    desNode->m_ref_pNodePreSibling = node;
    node->m_ref_pNodeNextSibling = desNode;
    node->m_ref_pNodeParent = desNode->m_ref_pNodeParent;
  } break;
  case HSNodeRelation::RELATION_FIRST_CHILD: {
    HSNode* firstChildNode = desNode->m_ref_pNodeFirstChild;
    if (firstChildNode) {
      firstChildNode->m_ref_pNodePreSibling = node;
      node->m_ref_pNodeNextSibling = firstChildNode;
    }
    desNode->m_ref_pNodeFirstChild = node;
    node->m_ref_pNodeParent = desNode;
    node->m_ref_pNodePreSibling = nullptr;
  } break;
  case HSNodeRelation::RELATION_LAST_CHILD: {
    HSNode* lastChildNode = GetLastChild(desNode);
    if (lastChildNode) {
      node->m_ref_pNodeParent = desNode;
      node->m_ref_pNodePreSibling = lastChildNode;
      lastChildNode->m_ref_pNodeNextSibling = node;
    } else {
      desNode->m_ref_pNodeFirstChild = node;
      node->m_ref_pNodeParent = desNode;
      node->m_ref_pNodePreSibling = nullptr;
    }
  } break;
  default:
    return HSNodeResult::RESULT_ERROR;
  }
  return HSNodeResult::RESULT_SUCCESS;
}

int HSForest::GetChildrenCount(const HSNode* node) const {
  if (!node)
    node = &m_soil;
  int sum = 0;
  const HSNode* nd = node->m_ref_pNodeFirstChild;
  while (nd) {
    ++sum;
    nd = nd->m_ref_pNodeNextSibling;
  }
  return sum;
}

bool HSForest::IsNodeInForest(const HSNode* node) const {
  if (!node)
    return false;
  while (node->m_ref_pNodeParent) {
    node = node->m_ref_pNodeParent;
  }
  return node == &m_soil;
}

bool HSForest::IsSibling(const HSNode* nodea, const HSNode* nodeb) const {
  if (!nodea || !nodea->m_ref_pNodeParent)
    return false;
  if (!nodeb || !nodeb->m_ref_pNodeParent)
    return false;

  return nodea->m_ref_pNodeParent == nodeb->m_ref_pNodeParent;
}

bool HSForest::IsDirectDependent(const HSNode* node, const HSNode* ancestorNode) const {
  if (ancestorNode) {
    while (node) {
      if (node == ancestorNode)
        return true;
      node = node->m_ref_pNodeParent;
    }
  }
  return false;
}

HSNode* HSForest::Traverse(const HSNode* node, bool begin) {
  if (begin) {
    m_ref_pNode = node ? node->m_ref_pNodeFirstChild : m_soil.m_ref_pNodeFirstChild;
    return m_ref_pNode;
  } else {
    if (m_ref_pNode) {
      if (m_ref_pNode->m_ref_pNodeFirstChild) {
        m_ref_pNode = m_ref_pNode->m_ref_pNodeFirstChild;
        return m_ref_pNode;
      } else if (m_ref_pNode->m_ref_pNodeNextSibling) {
        m_ref_pNode = m_ref_pNode->m_ref_pNodeNextSibling;
        return m_ref_pNode;
      } else {
        m_ref_pNode = m_ref_pNode->m_ref_pNodeParent;
        if (m_ref_pNode == node || m_ref_pNode == &m_soil)
          return nullptr;
        while (m_ref_pNode) {
          if (m_ref_pNode->m_ref_pNodeNextSibling) {
            m_ref_pNode = m_ref_pNode->m_ref_pNodeNextSibling;
            return m_ref_pNode;
          } else {
            m_ref_pNode = m_ref_pNode->m_ref_pNodeParent;
            if (m_ref_pNode == node || m_ref_pNode == &m_soil)
              return nullptr;
          }
        };
        return nullptr;
      }
    } else
      return nullptr;
  }
}

int HSForest::GetDepth(HSNode* node) const {
  int depth{FOREST_DEPTH_ROOT};
  HSNode* nd = node->m_ref_pNodeParent;
  while (nd) {
    if (nd == &m_soil)
      return depth;
    ++depth;
    nd = nd->m_ref_pNodeParent;
  }
  return FOREST_DEPTH_NOT_EXIST;
}

bool HSProcessor::IsDirectDependent(const HSNode* node, const HSNode* ancestorNode) {
  if (!ancestorNode)
    return false;
  while (node) {
    if (node == ancestorNode)
      return true;
    node = node->m_ref_pNodeParent;
  }
  return false;
}

#define _M_GET_ROOT(T)                                                                                                 \
  T _nPre{nullptr};                                                                                                    \
  while (node) {                                                                                                       \
    _nPre = node;                                                                                                      \
    node = node->m_ref_pNodeParent;                                                                                    \
  }                                                                                                                    \
  return _nPre;

HSNode* HSProcessor::GetRoot(HSNode* node) {
  _M_GET_ROOT(HSNode*)
}
const HSNode* HSProcessor::GetRoot(const HSNode* node) {
  _M_GET_ROOT(const HSNode*)
}

#define _M_GET_LAST_CHILD(T)                                                                                           \
  if (!node)                                                                                                           \
    return nullptr;                                                                                                    \
  T _n{node->m_ref_pNodeFirstChild};                                                                                   \
  T _nPre{nullptr};                                                                                                    \
  while (_n) {                                                                                                         \
    _nPre = _n;                                                                                                        \
    _n = _n->m_ref_pNodeNextSibling;                                                                                   \
  }                                                                                                                    \
  return _nPre;

HSNode* HSProcessor::GetLastChild(HSNode* node) {
  _M_GET_LAST_CHILD(HSNode*)
}
const HSNode* HSProcessor::GetLastChild(const HSNode* node){_M_GET_LAST_CHILD(const HSNode*)}

HSNode* HSProcessor::GetSiblingAt(HSNode* node, int offset) {
  while (offset != 0) {
    if (!node)
      return nullptr;
    if (offset > 0) {
      --offset;
      node = node->m_ref_pNodeNextSibling;
    } else {
      ++offset;
      node = node->m_ref_pNodePreSibling;
    }
  }
  return node;
}

void HSProcessor::Remove(HSNode* node) {
  if (!node)
    return;
  HSNode* pNode = node->m_ref_pNodeParent;
  HSNode* preNode = node->m_ref_pNodePreSibling;
  HSNode* nextNode = node->m_ref_pNodeNextSibling;

  /// rebuild sibling relation;
  if (preNode)
    preNode->m_ref_pNodeNextSibling = nextNode;
  if (nextNode)
    nextNode->m_ref_pNodePreSibling = preNode;

  /// rebuild parent relation;
  if (pNode && pNode->m_ref_pNodeFirstChild == node) {
    pNode->m_ref_pNodeFirstChild = nextNode;
  }

  node->m_ref_pNodeParent = nullptr;
  node->m_ref_pNodePreSibling = nullptr;
  node->m_ref_pNodeNextSibling = nullptr;
}

void HSProcessor::RemoveChildren(HSNode* node) {
  if (!node)
    return;
  while (node->m_ref_pNodeFirstChild) {
    Remove(node->m_ref_pNodeFirstChild);
  }
}

void HSProcessor::InsertAsFirstChild(HSNode* node, HSNode* desNode) {
  if (nullptr == node || nullptr == desNode)
    return;
  Remove(node);
  HSNode* firstChildNode = desNode->m_ref_pNodeFirstChild;
  if (firstChildNode) {
    firstChildNode->m_ref_pNodePreSibling = node;
    node->m_ref_pNodeNextSibling = firstChildNode;
  }
  desNode->m_ref_pNodeFirstChild = node;
  node->m_ref_pNodeParent = desNode;
}

void HSProcessor::InsertAsLastChild(HSNode* node, HSNode* desNode) {
  if (nullptr == node || nullptr == desNode)
    return;
  Remove(node);
  HSNode* lastChildNode = GetLastChild(desNode);
  if (lastChildNode) {
    node->m_ref_pNodeParent = desNode;
    lastChildNode->m_ref_pNodeNextSibling = node;
    node->m_ref_pNodePreSibling = lastChildNode;
  } else {
    desNode->m_ref_pNodeFirstChild = node;
    node->m_ref_pNodeParent = desNode;
  }
}
void HSProcessor::InsertAsNextSibling(HSNode* node, HSNode* desNode) {
  if (nullptr == node || nullptr == desNode)
    return;
  Remove(node);
  HSNode* nextNode = desNode->m_ref_pNodeNextSibling;
  node->m_ref_pNodeNextSibling = nextNode;
  if (nextNode)
    nextNode->m_ref_pNodePreSibling = node;
  desNode->m_ref_pNodeNextSibling = node;
  node->m_ref_pNodePreSibling = desNode;
  node->m_ref_pNodeParent = desNode->m_ref_pNodeParent;
}
void HSProcessor::InsertAsPreSibling(HSNode* node, HSNode* desNode) {
  if (nullptr == node || nullptr == desNode)
    return;
  Remove(node);

  HSNode* pNode = desNode->m_ref_pNodeParent;
  HSNode* preNode = desNode->m_ref_pNodePreSibling;

  node->m_ref_pNodePreSibling = preNode;
  node->m_ref_pNodeNextSibling = desNode;
  node->m_ref_pNodeParent = pNode;

  if (preNode)
    preNode->m_ref_pNodeNextSibling = node;
  else {
    if (pNode)
      pNode->m_ref_pNodeFirstChild = node;
  }
  desNode->m_ref_pNodePreSibling = node;
}
int HSProcessor::GetChildrenCount(const HSNode* node) {
  if (!node)
    return 0;
  int sum{0};
  const HSNode* nd = node->m_ref_pNodeFirstChild;
  while (nd) {
    ++sum;
    nd = nd->m_ref_pNodeNextSibling;
  }
  return sum;
}

HSNode* HSProcessor::Traverse(HSNode* rootNode, HSNode* pNode, HSNode* nNode, HSNode* cNode, bool begin) {
  HSNode* _retNode{nullptr};
  if (begin) {
    _retNode = rootNode->m_ref_pNodeFirstChild;
  } else {
    if (cNode) {
      _retNode = cNode;
    } else {
      if (nNode) {
        _retNode = nNode;
      } else {
        HSNode* _t{pNode};
        while (_t != rootNode) {
          if (_t->m_ref_pNodeNextSibling) {
            _retNode = _t->m_ref_pNodeNextSibling;
            break;
          } else {
            _t = _t->m_ref_pNodeParent;
          }
        }
      }
    }
  }

  if (_retNode) {
    pNode = _retNode->m_ref_pNodeParent;
    nNode = _retNode->m_ref_pNodeNextSibling;
    cNode = _retNode->m_ref_pNodeFirstChild;
  }
  return _retNode;
}
} // namespace basic
